// Copyright (C) Calum Grant 2008

#include "cppscript"
#include "dynamic/extensions.hpp"

#include <cstdlib>
#include <cstdio>


kingsley_heap::kingsley_heap() : m_allocated(0)
{
	for(int i=0; i<num_blocks; ++i)
	{
		m_blocks[i] = 0;
	}
}


kingsley_heap::~kingsley_heap()
{
	for(void ** a = m_allocated; a; )
	{
		void * to_free = a;
		a = *(void***)a;
		::free(to_free);
	}
}


namespace
{
	typedef unsigned long uint32;
	typedef long int32;

	// integer log2 of a float
	inline uint32 ilog2(float x)
	{
		uint32 ix = (uint32&)x;
		uint32 exp = (ix >> 23) & 0xFF;
		int32 log2 = int32(exp) - 127;

		return log2;
	}
}


void * kingsley_heap::malloc(std::size_t bytes)
{
	int cell = ilog2(float(bytes + sizeof(void**) - 1))+1;

	// GCC 4.2.3: If you put this line in the program works.
	printf("%d bytes allocated in cell %d\n", int(bytes), cell);

	for(int pop_block=cell; pop_block<num_blocks; ++pop_block)
	{
		void ** block = m_blocks[pop_block];
		if(block)
		{
			void ** next_block = *(void***)block;
			m_blocks[pop_block] = next_block;

			for(int push_block = pop_block-1; push_block>cell; --push_block)
			{
				next_block = (void**)((char*)block + (1<<push_block));
				*(void**)next_block = m_blocks[push_block];
				m_blocks[push_block] = next_block;
			}

			// Return the block
			*(void**)block = m_blocks + cell;
			return (char*)block + sizeof(void**);
		}
	}

	// There are no available blocks so allocate one from the main heap

	const int default_alloc_cell = 15;  // 1<<15 = 32KB
	int alloc_cell = std::max(cell, default_alloc_cell);

	cg::staticassert<sizeof(void**)<=16>();
	const int padding = 32 - sizeof(void**);

	void * new_block = ::malloc( (1<<alloc_cell)+padding );
	
	if(!new_block) throw std::bad_alloc();
	*(void**)new_block = m_allocated;
	m_allocated = (void**)new_block;

	//printf("Allocated new root block to cell %d\n", alloc_cell);

	void ** block = (void**)((char*)new_block + padding);
	m_blocks[alloc_cell] = block;
	*block = 0;
	
	return malloc(bytes);
}


void kingsley_heap::free(void*p)
{
	void ** block = (void**)((char*)p - sizeof(void**));
	void ** chain = *(void***)block;
	*block = *chain;
	*chain = block;
}


void kingsley_heap::defrag()
{
	// Maybe implement this sometime
}
